package org.example.leetcpde;

import org.example.Heap;
import org.junit.jupiter.api.Test;

import javax.imageio.metadata.IIOMetadataFormat;

public class search {

    @Test
    void run() {
                int[] nums = {4, 5, 6, 7, 0, 1, 2};
//        int[] nums = {6, 7, 0, 1, 2, 4, 5};
        int search = search(nums, 0);
        System.out.println(search);
    }

    public int search(int[] nums,
                      int target) {
        int len = nums.length;
        if (len == 0) {
            return -1;
        }

        if (len == 1) {
            return nums[0] == target ? 0 : -1;
        }

        for (int i = 0, j = len - 1, head = nums[0], tail = nums[len - 1]; i <= j; ) {
            int midIdx = (i + j) >> 1, midVal = nums[midIdx];
            if (midVal == target) {
                return midIdx;
            }

            if (head <= midVal) {
                if (head <= target && target <= midVal) {
                    j = midIdx - 1;
                } else {
                    i = midIdx + 1;
                }
            } else {
                if (midVal < target && target <= tail) {
                    i = midIdx + 1;
                } else {
                    j = midIdx - 1;
                }
            }
        }

        return -1;
    }
}
